<html>
<head><meta charset="utf-8"><title>partial_solution · t-cargo/PubGrub · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/index.html">t-cargo/PubGrub</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html">partial_solution</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="239877487"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239877487" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239877487">(May 22 2021 at 14:44)</a>:</h4>
<p>I'm in the process of rewriting the partial solution to get rid of the duality <code>history</code>/<code>memory</code> since it's something I had wanted to do for a looong time. I've all ready except the part with satisfiers which I'm dealing with now and giving me a headache ^^. I'll let you know if it goes well later today if I've found my way through.</p>



<a name="239879369"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879369" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879369">(May 22 2021 at 15:09)</a>:</h4>
<p>That is very cool! What is the plan?</p>



<a name="239879531"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879531" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879531">(May 22 2021 at 15:12)</a>:</h4>
<p>Right now this is my data structure:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="sd">/// The partial solution contains all package assignments,</span>
<span class="sd">/// organized by package and historically ordered.</span>
<span class="cp">#[derive(Clone)]</span><span class="w"></span>
<span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">PartialSolution</span><span class="o">&lt;</span><span class="n">P</span>: <span class="nc">Package</span><span class="p">,</span><span class="w"> </span><span class="n">V</span>: <span class="nc">Version</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">current_decision_level</span>: <span class="nc">DecisionLevel</span><span class="p">,</span><span class="w"></span>
<span class="w">    </span><span class="n">package_assignments</span>: <span class="nc">Map</span><span class="o">&lt;</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">PackageAssignments</span><span class="o">&lt;</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">V</span><span class="o">&gt;&gt;</span><span class="p">,</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="sd">/// Package assignments contain the potential decision and derivations</span>
<span class="sd">/// that have already been made for a given package,</span>
<span class="sd">/// as well as the intersection of terms by all of these.</span>
<span class="cp">#[derive(Clone)]</span><span class="w"></span>
<span class="k">struct</span> <span class="nc">PackageAssignments</span><span class="o">&lt;</span><span class="n">P</span>: <span class="nc">Package</span><span class="p">,</span><span class="w"> </span><span class="n">V</span>: <span class="nc">Version</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">smallest_decision_level</span>: <span class="nc">DecisionLevel</span><span class="p">,</span><span class="w"></span>
<span class="w">    </span><span class="n">highest_decision_level</span>: <span class="nc">DecisionLevel</span><span class="p">,</span><span class="w"></span>
<span class="w">    </span><span class="n">dated_derivations</span>: <span class="nb">Vec</span><span class="o">&lt;</span><span class="n">DatedDerivation</span><span class="o">&lt;</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">V</span><span class="o">&gt;&gt;</span><span class="p">,</span><span class="w"></span>
<span class="w">    </span><span class="n">assignments_intersection</span>: <span class="nc">AssignmentsIntersection</span><span class="o">&lt;</span><span class="n">V</span><span class="o">&gt;</span><span class="p">,</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="cp">#[derive(Clone)]</span><span class="w"></span>
<span class="k">pub</span><span class="w"> </span><span class="k">struct</span> <span class="nc">DatedDerivation</span><span class="o">&lt;</span><span class="n">P</span>: <span class="nc">Package</span><span class="p">,</span><span class="w"> </span><span class="n">V</span>: <span class="nc">Version</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">decision_level</span>: <span class="nc">DecisionLevel</span><span class="p">,</span><span class="w"></span>
<span class="w">    </span><span class="n">cause</span>: <span class="nc">IncompId</span><span class="o">&lt;</span><span class="n">P</span><span class="p">,</span><span class="w"> </span><span class="n">V</span><span class="o">&gt;</span><span class="p">,</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="239879723"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879723" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879723">(May 22 2021 at 15:14)</a>:</h4>
<p>The major advantage is that accessing the right packages during conflict resolution is now a direct access, there is no need to go through the whole history to get packages relevant to a satisfied incompatibility.</p>



<a name="239879809"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879809" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879809">(May 22 2021 at 15:15)</a>:</h4>
<p>The main disadvantages that's giving me the headache is that I can't figure out how to actually perform conflict resolution if I don't have a unique reference index for each assignment.</p>



<a name="239879900"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879900" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879900">(May 22 2021 at 15:17)</a>:</h4>
<p>Can we use <code>decision_level</code>?</p>



<a name="239879908"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879908" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879908">(May 22 2021 at 15:17)</a>:</h4>
<p>I've been thinking quite a lot and I feel it's not easy because if packages are split by key in a map, it's hard to have more precise global order than what the decision level gives</p>



<a name="239879944"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239879944" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239879944">(May 22 2021 at 15:17)</a>:</h4>
<p>and with only decision level, the annoying thing is this:</p>
<blockquote>
<p>Find the earliest assignment in the partial solution before satisfier such that incompatibility is satisfied by the partial solution up to and including that assignment plus satisfier. Call this previousSatisfier</p>
</blockquote>



<a name="239880005"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880005" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880005">(May 22 2021 at 15:18)</a>:</h4>
<p>Because I can only identify "a package that has the same decision level than the satisfier" and not "the satisfier"</p>



<a name="239880051"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880051" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880051">(May 22 2021 at 15:19)</a>:</h4>
<p>hmmm....</p>



<a name="239880054"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880054" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880054">(May 22 2021 at 15:19)</a>:</h4>
<p>This results in the fact that if two different packages at the same decision level are potential satisfiers, I might end up picking the "wrong one"</p>



<a name="239880063"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880063" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880063">(May 22 2021 at 15:19)</a>:</h4>
<p>So I've been thinking "is there a wrong one actually"?</p>



<a name="239880163"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880163" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880163">(May 22 2021 at 15:20)</a>:</h4>
<p>I don't think so. the order we find incompats to be almost satisficed is not guaranteed.</p>



<a name="239880404"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880404" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880404">(May 22 2021 at 15:24)</a>:</h4>
<p>And there is this situation:</p>
<ul>
<li>package a has assignments a1 and a2</li>
<li>package b has assignments b2 only where a2 and b2 are potential satisfiers (same decision level)</li>
</ul>
<p>If I pick a2, there will be a previous satisfier since a1 exists, but if the actual satisfier was a2 and I pick b2 I won't find a previous satisfier since there is no package earlier that would satisfy package b ...</p>



<a name="239880447"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880447" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880447">(May 22 2021 at 15:25)</a>:</h4>
<p>Does it makes sense?</p>



<a name="239880540"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880540" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880540">(May 22 2021 at 15:26)</a>:</h4>
<p>I think so.</p>



<a name="239880547"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880547" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880547">(May 22 2021 at 15:27)</a>:</h4>
<p>I could also not bother too much and just store a unique index in addition to the decision level for each assignment. Make it work then improve</p>



<a name="239880583"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880583" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880583">(May 22 2021 at 15:27)</a>:</h4>
<p>That seams a resendable pan.</p>



<a name="239880647"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880647" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880647">(May 22 2021 at 15:28)</a>:</h4>
<p>If the performance is horrible, that's not by removing that u32 index that miracles will happen. But if it's good, we can think of improvements later</p>



<a name="239880676"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880676" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880676">(May 22 2021 at 15:29)</a>:</h4>
<p>alright I'll try that</p>



<a name="239880836"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239880836" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239880836">(May 22 2021 at 15:31)</a>:</h4>
<p>elm and synthetic do not have much backtracking. so brake even is a win for them.</p>



<a name="239896228"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239896228" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239896228">(May 22 2021 at 19:55)</a>:</h4>
<p>I've pushed what I got even though it does not pass the tests. I must have introduced a bug but my head is not clear enough to spot it anymore. The interesting stuff is in <code>partial_solution_bis</code>. I haven't removed anything, but by the end of this PR, we should be able to remove <code>memory</code> and <code>assignment</code> modules to be left with just <code>partial_solution_bis</code> renamed into <code>partial_solution</code>.</p>



<a name="239898247"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239898247" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239898247">(May 22 2021 at 20:32)</a>:</h4>
<p>A possible debugging approach, add a <code>partial_solution_both</code> that wraps both the old and new versions and asserts that they return the same thing for all methods.</p>



<a name="239898782"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239898782" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239898782">(May 22 2021 at 20:41)</a>:</h4>
<p>that's smart! I might try tomorrow if I find the time!</p>



<a name="239990084"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/239990084" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#239990084">(May 24 2021 at 00:45)</a>:</h4>
<p>Ok looking into witch impl of <code>previous_satisfier</code> is "correct", I looked at:<br>
the blog: <a href="https://medium.com/@nex3/pubgrub-2fb6470504f#cbda">https://medium.com/@nex3/pubgrub-2fb6470504f#cbda</a><br>
the docs: <a href="https://github.com/dart-lang/pub/blob/master/doc/solver.md#conflict-resolution">https://github.com/dart-lang/pub/blob/master/doc/solver.md#conflict-resolution</a><br>
and the impl: <a href="https://github.com/dart-lang/pub/blob/291705ca0b9632cb945dd39493dd5b9db41b897a/lib/src/solver/version_solver.dart#L201">https://github.com/dart-lang/pub/blob/291705ca0b9632cb945dd39493dd5b9db41b897a/lib/src/solver/version_solver.dart#L201</a></p>
<p>and I don't think any two of them are the same thing!</p>



<a name="240019061"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/240019061" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#240019061">(May 24 2021 at 08:08)</a>:</h4>
<p>I've tried to read carefully pub impl and I think it's the same as the docs, just implemented a tiny bit weirdly because she does only one pass and thus need the special treatment at <a href="https://github.com/dart-lang/pub/blob/291705ca0b9632cb945dd39493dd5b9db41b897a/lib/src/solver/version_solver.dart#L247">https://github.com/dart-lang/pub/blob/291705ca0b9632cb945dd39493dd5b9db41b897a/lib/src/solver/version_solver.dart#L247</a> in order to correctly identify that previous satisfier. While we do a second pass where we initialize the accum term with the satisfier term so we don't need that special treatment.</p>



<a name="240019814"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/240019814" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#240019814">(May 24 2021 at 08:17)</a>:</h4>
<p>Also, I tried displaying some stats for the resolution of the package <code>"zuse-Minor(4)-All-FEATURES"</code> and I obtained the following:</p>
<div class="codehilite"><pre><span></span><code>With your approach:

    Final state stats:
    Size of the incompatibility store: 152
    Size of saved incompatibilities: 282

    Partial solution stats:
    next_global_index: 174
    Number of derivations: 48

With the approach that choose the &quot;correct&quot; previous decision level:

    Final state stats:
    Size of the incompatibility store: 205
    Size of saved incompatibilities: 393

    Partial solution stats:
    next_global_index: 386
    Number of derivations: 53
</code></pre></div>
<p>So I think the intuition saying that applying a "rule of resolution" to find the previous cause of a satisfier package that is seen for the first time (the behavior change concerns only situations where there is no previous derivation to the one of the satisfier for that package) instead of backtracking (which would happen if some other package has a lower satisfier level) is a good heuristic. Because it essentially says: "try first to find the reason why we have that derived package term that we see for the first time"</p>



<a name="240165994"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/240165994" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#240165994">(May 25 2021 at 10:08)</a>:</h4>
<blockquote>
<p>So I think the intuition saying that applying a "rule of resolution" to find the previous cause of a satisfier package that is seen for the first time</p>
</blockquote>
<p>Currently, the only way a term can appear for the first time is via an incompatibility (i12) generated by a previous package P1 depending on that package P2 (of the satisfied term). So essentially, if the satisfier is the first term of a given package P2, with the current rules of how terms can be generated, it means that the decision (picking P1) that lead to the incompatibility (i12) that lead to that first satisfier term was probably a wrong decision.</p>
<p>So instead of backtracking right away, we first apply the rule of resolution (<a href="https://pubgrub-rs-guide.netlify.app/internals/incompatibilities.html#rule-of-resolution">https://pubgrub-rs-guide.netlify.app/internals/incompatibilities.html#rule-of-resolution</a>) between the current incompat and the incompat (i12) cause of that satisfier term. Since they both have P2 in common and the term of the new one satisfies the term of  the old one, we are in the simple situation of the type (Ta, -Tb) and (Tb, -Tc) implies (Ta, -Tc). And now we pick that derived new incompatibility and continue conflict resolution.</p>
<p>So essentially, the changes you introduced is like a shortcut to more general incompatibilities that works thanks to the fact that the only way a package term can appear for the first time is to be a derived term from the incompatibility generated by a package dependency.</p>
<p>The question is, if eventually we allow more ways for incompatibilities to appear (like just specifying forbidden versions, or whatever) would those new ways will be compatible with that shortcut? Or will it lead to unwanted behaviors (like infinite loop for example)?</p>



<a name="240328481"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/240328481" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#240328481">(May 26 2021 at 13:58)</a>:</h4>
<p>Let me see if I can talk thru an example.<br>
In order for a incompat to have one term, (and not be root) it must be <code>NoVersions</code> or  <code>UnavailableDependencies</code>. Something like <code>Negative(bad=1.0.0)</code>.<br>
In order for that to be satisfied the intersected term for <code>bad</code> must be <code>Positive(bad=1.0.0)</code>.<br>
In order for there to be only one assignment to the partial solution related to <code>bad</code>, it must be a dependency on <code>bad</code>. Something like <code>foo 1.0.0 depends on bad 1.0.0</code>.<br>
So the "rule of resolution" does seam like the next logical step. In this example giving us <code>Negative(foo=1.0.0)</code></p>



<a name="240328957"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/240328957" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#240328957">(May 26 2021 at 14:01)</a>:</h4>
<p>I don't see how that logic will change with any of the other kinds of incompatibilities I can think of adding. But we can change the code here when we add the new incompatibilities if it is making trouble.</p>



<a name="243051209"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243051209" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243051209">(Jun 17 2021 at 17:09)</a>:</h4>
<p>Sorry for going silent about this project for a while. I have been doing research trying to figure out what invariants the code has, buy adding debug_asserts, and by reading up on other SAT solvers. I think I am getting somewhere with understanding <code>previous_satisfier</code>. But can't quite get it in words yet.</p>



<a name="243268574"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243268574" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243268574">(Jun 19 2021 at 20:53)</a>:</h4>
<p>no worry ^^. I'm quite silent too. We have had two interns arriving for the summer so I've had a bit more stuff to do than usual anyway. I'll try making progress on the advanced deps provider docs tomorrow. How is your computer doing?</p>



<a name="243268644"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243268644" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243268644">(Jun 19 2021 at 20:54)</a>:</h4>
<p>Also, I'll probably be radio silent starting from next weekend until 14th of July</p>



<a name="243270149"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243270149" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243270149">(Jun 19 2021 at 21:33)</a>:</h4>
<blockquote>
<p>How is your computer doing?</p>
</blockquote>
<p>The tiny little $3 south bridge fan is broken. It is not a standard part. The manufacturer claims that it is absolutely necessary and I should not turn on the computer without it. So they will be happy to send me a replacement, as soon as they get them back in stock. But they don't know when that will be.</p>



<a name="243270218"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243270218" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243270218">(Jun 19 2021 at 21:35)</a>:</h4>
<blockquote>
<p>I'll try making progress on the advanced deps provider docs tomorrow.</p>
</blockquote>
<p>I am getting distracted by a new plan to impl the RangeTrait for Cargos Semver. I think this may work.</p>



<a name="243291368"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/260232-t-cargo/PubGrub/topic/partial_solution/near/243291368" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthieu Pizenberg <a href="https://rust-lang.github.io/zulip_archive/stream/260232-t-cargo/PubGrub/topic/partial_solution.html#243291368">(Jun 20 2021 at 07:36)</a>:</h4>
<p><span class="user-mention silent" data-user-id="120179">Eh2406</span> <a href="#narrow/stream/260232-t-cargo.2FPubGrub/topic/partial_solution/near/243270149">said</a>:</p>
<blockquote>
<blockquote>
<p>How is your computer doing?</p>
</blockquote>
<p>The tiny little $3 south bridge fan is broken. It is not a standard part. The manufacturer claims that it is absolutely necessary and I should not turn on the computer without it. So they will be happy to send me a replacement, as soon as they get them back in stock. But they don't know when that will be.</p>
</blockquote>
<p>That sucks :(</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>